未分類

Reverse String II

Go, LeetCode, String

Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

For Example:

1
2
Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

  1. The string consists of lower English letters only.
  2. Length of the given string and k will in the range [1, 10000]
提示 解題應用
String 規律觀查

Default:

1
2
3
func reverseStr(s string, k int) string {
}

解答思路:

這題主要是做字串上規律的觀查，字串中前k個字做倒轉，下一組k個字就不需要，而再下一組k就再做倒轉，換句話說就是如果以一組一組來看的話index值除以k如果商數為0就在第一組，商數為1就在第二組，商數為2就在第三組，這麼說只要商數為偶數該字母就必然是歸類於做倒轉的字串，在得知這樣規則的前提下就可以沒有壓力的解決問題。

程式碼解說:

一開始從字串一一取出字母，正如先前有的結論，將index值除以k先知道落在哪一組，再將商數與2相除取餘數，如果餘數為0表示商數為偶數要做倒轉，這時就將倒轉註記為true，否則餘數為1的情況則註記為false，再將先前已經暫存倒轉的字串加入結果之中並清空暫存，而再決定好是否倒轉後就要開始處理每個字母，因為golang取出字母為rune值所以要先轉成字串再開始動作，接著如果該字母需要倒轉，就存在暫存字串的開頭，待所有該組字母皆倒轉完畢(在先前的判斷倒轉註記為false)才整組放入結果，而如果該字母不需要倒轉，則直則依序放入結果後頭即可，最後待遍歷字串結束後，因為有可能暫存字串還留有尚未放入結果的字元，所以最後要再一次將暫存字串放入結果後頭之中才做回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var str string
var tmp string
var result string
var reverse bool
for i, v := range s {
	if (i/k)%2 == 0 {
		reverse = true
	} else {
		reverse = false
		result += tmp
		tmp = ""
	}
	str = string(v)
	if reverse {
		tmp = str + tmp
	} else {
		result += str
	}
}
result += tmp
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func reverseStr(s string, k int) string {
	var str string
	var tmp string
	var result string
	var reverse bool
	for i, v := range s {
		if (i/k)%2 == 0 {
			reverse = true
		} else {
			reverse = false
			result += tmp
			tmp = ""
		}
		str = string(v)
		if reverse {
			tmp = str + tmp
		} else {
			result += str
		}
	}
	result += tmp
	return result
}

總結:

要將一字串中前k個字做倒轉，下一組k個字就不需要，而再下一組k就再做倒轉…等等以此類推，如果以一組一組來看的話index值除以k如果商數為0就在第一組，商數為1就在第二組，商數為2就在第三組，這麼說只要商數為偶數該字母就必然是歸類於做倒轉的字串，在得知這樣規則的前提下就可以沒有壓力的解決問題。

分享到